package leetcode.tree;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Lc1438 {

    public int longestSubarray(int[] nums, int limit) {

        TreeMap<Integer, Integer> map = new TreeMap<>(); //num:index
        map.put(nums[0], 0);
        int minIndex = 0; //记录treemap中连续数组的最小下标值
        int ans = 1;

        for (int i = 1; i < nums.length; i++) {
            int left = nums[i] - limit - 1;
            int right = nums[i] + limit + 1;
            Integer ceil = map.ceilingKey(right); // 大于等于right的最小值是否存在
            Integer floor = map.floorKey(left); // 小于等于left的最大值是否存在
            if (ceil == null && floor == null) {
                ans = Math.max(ans, i - minIndex + 1);
                map.put(nums[i], i);
            } else { //map中存在绝对查大于limit的值
                while (!map.isEmpty() && ceil != null) {
                    minIndex = Math.max(minIndex, map.get(ceil) + 1); //更新tree中连续数组的最小下标
                    map.remove(ceil);
                    ceil = map.ceilingKey(right);
                }
                while (!map.isEmpty() && floor != null) {
                    minIndex = Math.max(minIndex, map.get(floor) + 1);
                    map.remove(floor);
                    floor = map.floorKey(left);
                }
                map.put(nums[i], i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Lc1438 lc1438 = new Lc1438();
        int[] a = {10,1,2,4,7,2};

        System.out.println(lc1438.longestSubarray(a, 5));


    }




}
